package com.LeetCode.StackAndHeap;

import java.util.HashSet;
import java.util.Stack;

/**
 * 移除无效括号
 */
public class RemoveUnuseBrackets {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stack = new Stack<>();
        HashSet<Integer> indexToRemove = new HashSet<>();
        StringBuilder res = new StringBuilder();

        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            }else if(s.charAt(i) == ')'){
                if(stack.isEmpty()){
                    indexToRemove.add(i);
                }else{
                    stack.pop();
                }
            }
        }

        //可能有的左括号'('是还没被匹配到的
        while(!stack.isEmpty()) indexToRemove.add(stack.pop());
        for(int i = 0; i<s.length(); i++){
            if(!indexToRemove.contains(i)){
                res.append(s.charAt(i));
            }
        }
        return res.toString();
    }
}
